/*
Problem:
Assemble:
Anthor:     Alchemist
Date:
Tag:
Difficulty:
Description:
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

const int maxn = 1000000 + 2;
int al[maxn] = {0};
int f[maxn][30]={0};
int n,q;

void init()
{
    cin >> n;
    n ++;
    for(int i = 1; i <= n ; i ++)
    {
        scanf("%d",&f[i][0]);
    }
    int k = log(n)/log(2);
    for(int i = 1; i <= k; i ++)
    {
        int l = 1 << (i - 1);
        int e = (1 << i) - 1;
        for(int j = 1;j + e <= n ; j ++)
        {
            f[j][i] = max(f[j][i - 1], f[j + l][i - 1]);
        }
    }
}

int main()
{
    freopen("climb.in","r",stdin);
    freopen("climb.out","w",stdout);
    init();
    int a,b;
    cin >> q;
    for(int i = 0; i < q; i ++)
    {
        scanf("%d%d",&a,&b);
        a ++;
        b ++;
        int k = log(b-a+1)/log(2);
        cout << max(f[a][k], f[b - (1 << k) + 1][k]) << endl;
    }
    return 0;
}
